package datastructure.sort;

import datastructure.utils.Common;

/**
 * 使用 <span color="green">最大堆</span>原地对数组进行排序
 * @author or2
 * @date 2021/8/6 10:42
 */
public class MaxHeap {

    public static  <E extends Comparable<E>> void sort(E[] arr) {
        int length = arr.length;
        if (length <= 1) {
            return;
        }
//        使当前数组满足最大堆条件
        int leftChild = (length << 1) + 1;
        for (int i = leftChild; i >= 0; i--) {
            siftDown(arr, i, length);
        }
//        交换首尾元素, 进行下一轮下沉, 直至数组有序
        for (int i = length - 1; i >= 0; i--) {
            Common.swapArray(arr, 0, i);
            siftDown(arr, 0, i);
        }
    }

    /**
     * 对 {@code arr} 数组, 从 {@code index} 索引处进行下沉, 下沉规模 {@code length}
     *
     * @param arr    数组
     * @param index  数组的索引
     * @param length 下沉的规模
     * @param <E>    extends Comparable<E>
     */
    private static <E extends Comparable<E>> void siftDown(E[] arr, int index, int length) {
        while (true) {
            int liftChild = (index << 1) + 1;
            if (liftChild >= length - 1) {
                return;
            }
//        找到最大的孩子
            int p = liftChild;
            if (liftChild + 1 < length && arr[liftChild + 1].compareTo(arr[liftChild]) > 0) {
                p = liftChild + 1;
            }
//        若孩子都小于当前结点, 符合条件, 结束
            if (arr[p].compareTo(arr[index]) < 0) {
                return;
            }
//        若不符合堆条件, 交换, 进行下一轮下沉
            Common.swapArray(arr, p, index);
            index = p;
        }
    }
}
